package com.example.demo.algorithm.heap;

public class HeapSort {

    /**
     * 判断i处的值是否小于J处的值
     *
     * @param i
     * @param j
     * @return
     */
    private static boolean less(Comparable[] heap, int i, int j) {
        return heap[i].compareTo(heap[j]) < 0;
    }

    /**
     * 交换i和j处的值
     */
    private static void exch(Comparable[] heap, int i, int j) {
        Comparable temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    /**
     * 构造堆
     *
     * @param source
     * @param heap
     */
    private static void createHeap(Comparable[] source, Comparable[] heap) {
        //把source的元素拷贝到heap中，heap中的元素就形成一个无序的堆
        System.arraycopy(source, 0, heap, 1, source.length);
        //对堆中的元素做下沉调整（从长度的一半处开始，往索引处扫描）
        for (int i = (heap.length) / 2; i > 0; i--) {
            sink(heap, i, heap.length - 1);
        }
    }

    /**
     * 对source数组中的数据从小到大排序
     *
     * @param source
     */
    public static void sort(Comparable[] source) {
        //构建堆
        Comparable[] heap = new Comparable[source.length + 1];
        createHeap(source, heap);
        //定义一个变量，记录未排序中最大的索引
        int N = heap.length - 1;
        //通过循环，交换1索引的元素和排序的元素中最大的索引处的元素
        while (N != 1) {
            exch(heap, 1, N);
            //交换完成后最大元素所在的索引，让它不参与堆得下沉调整
            N--;
            //需要对索引1处的元素进行堆得下沉调整
            sink(heap, 1, N);
        }
        //把heap中的元素复制到source中
        System.arraycopy(heap, 1, source, 0, source.length);
    }

    /**
     * 对heap堆中，堆target处的元素做下沉，范围是0~range
     *
     * @param heap
     * @param target
     * @param range
     */
    private static void sink(Comparable[] heap, int target, int range) {
        while (2 * target <= range) {
            //找到k处的子节点的最大值
            int maxchileIndex = 2 * target;
            if (2 * target + 1 <= range) {
                if (less(heap, 2 * target, 2 * target + 1)) {
                    maxchileIndex = 2 * target + 1;
                }
            }
            //比较当前节点的值和较大子节点的值
            if (!less(heap, target, maxchileIndex)) {
                break;
            }
            //当前节点的值小于较大子节点的值则交换
            exch(heap, target, maxchileIndex);
            //变换target的值
            target = maxchileIndex;
        }
    }

}
